/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import java.lang.IllegalArgumentException
import java.math.BigInteger

/**
 * An addressable radix heap for double keys. The heap stores double keys sorted
 * according to the [natural ordering][Comparable] of its keys. A
 * radix heap is a monotone heap, especially designed for algorithms (such as
 * Dijkstra) which scan elements in order of nondecreasing keys.
 *
 *
 *
 * Note that this implementation uses the fact that the IEEE floating-point
 * standard has the property that for any valid floating-point numbers a and b,
 * a&lt;=b if and only if bits(a)&lt;= bits(b), where
 * bits(x) denotes the re-interpretation of x as an unsigned integer
 * (long in our case).
 *
 *
 *
 * The implementation use arrays in order to store the elements. Operations
 * `insert` and `findMin` are worst-case constant time. The cost of
 * operation `deleteMin` is amortized O(logC) assuming the radix-heap
 * contains keys in the range [0, C] or equivalently
 * [a,a+C]. Note, however, that C here depends on the distance of the
 * minimum and maximum value when they are translated into unsigned longs.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @author Dimitrios Michail
 *
 * @param <V>
 * the type of values maintained by this heap
 *
 * @see Serializable
</V> */
class DoubleRadixAddressableHeap<V>(minKey: Double, maxKey: Double) : AbstractRadixAddressableHeap<Double, V>() {
    /**
     * Constructs a new heap which can store values between a minimum and a
     * maximum key value (inclusive).
     *
     * It is important to use the smallest key range as the heap uses O(logC)
     * where C=maxKey-minKey+1 buckets to store elements. Moreover, the
     * operation `deleteMin` requires amortized O(logC) time.
     *
     * @param minKey
     * the non-negative minimum key that this heap supports
     * (inclusive)
     * @param maxKey
     * the maximum key that this heap supports (inclusive)
     * @throws IllegalArgumentException
     * if the minimum key is negative
     * @throws IllegalArgumentException
     * if the maximum key is less than the minimum key
     */
    init {
        if (!java.lang.Double.isFinite(minKey) || minKey < 0.0) {
            throw IllegalArgumentException("Minimum key must be finite and non-negative")
        }
        this.minKey = minKey
        this.lastDeletedKey = minKey
        if (!java.lang.Double.isFinite(maxKey) || maxKey < minKey) {
            throw IllegalArgumentException("Maximum key must be finite and not less than the minimum")
        }
        this.maxKey = maxKey

        // compute number of buckets
        val minKeyAsBigInt: BigInteger? = UnsignedUtils.unsignedLongToBigInt(java.lang.Double.doubleToLongBits(minKey))
        val maxKeyAsBigInt: BigInteger? = UnsignedUtils.unsignedLongToBigInt(java.lang.Double.doubleToLongBits(maxKey))
        val diff: BigInteger = maxKeyAsBigInt!!.subtract(minKeyAsBigInt)
        val numBuckets: Int = 2 + 1 + diff.bitLength()

        // construct representation
        //this.buckets = (java.lang.reflect.Array.newInstance(Node::class.java, numBuckets) as Array<Node?>?)!!
        this.buckets = arrayOfNulls(numBuckets)
        this.size = 0
        this.currentMin = null
    }

    /**
     * {@inheritDoc}
     */
    override fun compare(o1: Double, o2: Double?): Int {
        /*
         * Convert to IEEE and compare as unsigned
         */
        val x: Long = java.lang.Double.doubleToLongBits(o1) xor Long.MIN_VALUE
        val y: Long = java.lang.Double.doubleToLongBits(o2!!) xor Long.MIN_VALUE

        // assert
        if (o1 < o2) {
            assert(x < y)
        } else if (o1 == o2) {
            assert(x == y)
        } else {
            assert(x > y)
        }

        return if ((x < y)) -1 else (if ((x == y)) 0 else 1)
    }

    /**
     * {@inheritDoc}
     */
    override fun msd(a: Double, b: Double?): Int {
        /*
         * For this to work, arithmetic must be unsigned
         */
        val ux: Long = java.lang.Double.doubleToLongBits(a)
        val uy: Long = java.lang.Double.doubleToLongBits(b!!)
        if (ux == uy) {
            return -1
        }
        val d: Double = UnsignedUtils.unsignedLongToDouble(ux xor uy)
        return Math.getExponent(d)
    }

    companion object {
        private val serialVersionUID: Long = 1
    }
}
